“Enigma” is the name of a series of electro-mechanical rotor cipher machines developed and used in the early to mid 20th century. It was invented by the German engineer Arthur Schebius at the end of WWI. In this article we will introduce (1) how the Enigma machine the Germans used before the Invasion of Poland works and (2) how Polish codebreakers deciphered it.
Background
The Axis powers used the Enigma machine to encipher secret intelligence. However, the Polish mathematician and cryptologist Marian Rejewski reconstructed it in 1932. After Rejewki had reconstructed Enigma, Polish codebreakers were able to decipher the Enigma enciphered messages. That is to say, the polish were able to eavesdrop Germany’s secret intelligence for about 7 years until 1939, the Invasion of Poland. In fact, if the Germans were to change their message keys more often, Enigma should have been unbreakable using the Polish deciphering method we are going to introduce, but they didn’t realize the importance of it until 1939.
Introduction to How to Use Enigma
The Enigma Machine
Here is a picture of the structure of the Enigma used before 1939. It has three rotors, a plugboard, a keyboard and a lampboard. The keyboard is for inputting messages, and the lampboard is for outputting encoded messages, while the rotors and the plugboard are for encoding input messages.
First, every month you will get a key sheet from someone in charge of it. On this key sheet you have all the information about how you should set up the Enigma every day.
This is a key sheet.
With the information you set up the sequence of the three rotors, the number position of each rotor, and the plugboard (we will talk about this in the next section). After everything is set up, you should randomly pick up three letters as your new message key. Say you picked up TGS as your new message key, you type TGS twice in case of mistyping and send the Enigma encoded message to your comrades. Your comrades should have set up their Enigma using the same monthly-changed key sheet as yours. Once they receive your encoded message they will decode it using Enigma and rest it using the new message key TGS.
Then you set the rotor to your new key and encode messages you want to send to your comrades.
How Does the Enigma Work
Rotor
Inside of a Rotor
The picture above is an image of the structure of the rotors. Every number on the ring represents a letter, and the green wires help us do the single letter substitution (e.g. After you input a letter A, Enigma will output a letter D).
Three Rotors.
We have three rotors in a line, and we can change the sequence of rotors (e.g. the third rotor in the first position and the first rotor in the second position, etc.). Everytime we input a letter, the leftmost rotor will rotate one position (e.g. input A will output E instead of D). After the leftmost rotor does a full rotation, the middle rotor will rotate one position, and after the middle rotor does a full rotation, the rightmost rotor will rotate for one position. So here we have \(26^3\) possible substitution for a single letter input.
Plugboard
Plugboard.
The plugboard is a very powerful part of the Enigma machine. We can connect two letters in the keyboard using a wire and thus swap the two letters during the encoding process. For example, in the picture, we have A connected to J, so every time A is pressed in the keyboard, the letter A will be transferred into J first and then encoded by the machine.
Setting
This is a key sheet.
The leftmost column in the key sheet tells us the sequence of the rotors, the second column tells us the initial letter on the rotor rings, and the third column tells all the plugboard pairs.
Reflector
The reflector is another important part in the Enigma machine. It makes the encoding process self-reversible, which makes the machine not only an encipher, but also a decipher, given the exactly same setting. For example, after you set up the machine according to the daily key, typing A will give you the encoded letter E, and typing E will give you the decoded letter A. Also, the reflector is a trick to make sure the input messages will not be encoded as itself, because in the reflector every letter is connected to the letter other than itself by a wire. But this characteristic turned out to be a leak for the enigma machine, since it will reduce the possibility by a large amount.
Encoding Process
Here is a process diagram for encoding a letter in the Enigma machine. We type letter T in the keyboard, and the signal will go through the plugboard, be changed into K, and go through the three rotors one by one. When the signal arrives at the reflector, it will be connected to another fixed joint. The signal which comes out from the reflector will go through the same process with opposite direction and, finally, G in the lightboard will light up. Self-reversible means given exactly same setting, if you type G in the keyboard, T will light up in the lightboard. That is how you decipher the secret intelligence.
Evaluation of the Enigma
For the permutation of the position of rotors, we have \(3!\) possible combinations, the possibilities created by the 3 rotors to change letters is \(26*26*26=17576\), and the possibility of plugboard with 6 plugs is \(100,391,791,500\). In total we have \(17576*6*100,391,791,500 = 10,000,000,000,000,000\) possibilities. Given this huge possibility, it’s impossible to decipher the text by violent cracking.
How to Decode the Enigma
Substitution Function
The first thing to crack the Enigma is to figure out the daily key. The polish took advantage of a mathematical method called the substitution function. Suppose the message key is XYZ, and after encoding (typing twice) it becomes HGABLE. Therefore, we can get a series of equations \[X(A0)=H\] \[Y(A1)=G\] \[Z(A2)=A\] \[X(A3)=B\] \[Y(A4)=L\] \[Z(A5)=E\] where A0, A1, …, A5 are the subsitution functions that map the input letter to the output letter on the right. Since the enigma is self-reversible, we can say that \[X(A0)(A0)=X\] Plugging this property in the 4th equation above, we get \[X(A0)(A0)(A3)=B\] Then we can replace \(X(A0)\) with \(H\), as shown in the 1st equation. We get \[H(A0)(A3)=B\]
We notice that X disappeared. The final equation left us with no letter from the message key, which tells us that on this particular day, \(H\) is turned into \(B\) using the substitution function \((A0)(A3)\). Therefore, we know that \((A0)(A3)\) is the substitution function for this day.
Knowing the daily key and substitution function, we may think it’s possible to violently crack the machine by trying all the possibilities of the initial rotor setting and see which setting gives us the substitution function \((A0)(A3)\). But this is only possible without the existence of the plugboard, and it will only take about 3 hours, using 100 enigma, 100 people, and 10 seconds per try. However, the plugboard enlarges the possibility by 100,391,791,500, so there must be a way to eliminate the effect of the plugboard, which Rejeweski actually accomplished in a smart way.
Cycle Group
Rajeweski found an important property between the plain text and the encoded text, the cycle group. See below, suppose the first line denotes plain text and the second line is the encoded text \[A B C D E F G H\] \[C H E F A B D G\] The cycle groups for the above relationship are therefore \((A, C, E)\) and \((B, H, G, D, F)\) Notice that A from plain text encodes to C, and C from plain text encodes to E, then E encodes back to A, so this constructs a cycle group, similar for \((B, H, G, D, F)\).
An important feature of the cycle group is called “links.” Links are the lengths of the cycle group. For example \((A, C, E)\) has link of 3, and \((B, H, G, D, F)\) has link of 5. Suppose that from the substitution function \((A0)(A3)\), we get a matching relationship similar to the example above, so that each letter is mapped to another. Then we can figure out the cycle groups of \((A0)(A3)\), let’s say thay are \[(A, C, M, Y, N, Z, Q, D, P, D, O) (E, U, I, S, G) (F, T, H, R) (J, V) (K, W) (L, X)\] where they have links of 11, 5, 4, 2, 2, 2, respectively. The Polish then took advantage of the leak of the plugboard, which is that a wire swaps a pair of letters. They found that swapping any two letters in the cycle groups will not change the links of the cycle groups, hence the links are unique to a set of cycle groups. So once we have the information about cycle groups and their links, we no longer consider the effect of the plugboard because it doesn’t change our result. Thus, we get rid of the plugboard.
Cracking Process
The Polish spent one year to sort the links of the cycle groups according to the initial setting of the Enigma. Specifically, they matched each set of links to several possible initial settings, and constructed a catalogue for those information. To crack the machine, first, they use the first 6 keys to find out the substitution functions as well as the cycle groups, then they have the information of the links, then they can at least know the range of initial rotor settings they can try by referring to the catalogue. After that, they tried all the possible initial settings and violently cracked, so that they got the initial setting of the rotors.
The arrangement of the plugboard is also essential in the deciphering process. To crack the plugboard, they first set up the Enigma using the initial rotor setting they figured out from above, then without plugging in the plugboard, they input some enciphered message and see how the letters are swapped. This makes use of relatively simple encryption, so it’s easy to figure out which 6 pairs of letters are swapped. So far, the Polish have all the initial settings of the Enigma, and are thus ready to decode any encoded messages from Germany.
German Updated Enigma
To prepare for the Invasion of Poland, the Germans secretly updated the Enigma so that it became even harder to crack. Specifically, 3 rotors were updated to 5 rotors, the daily key was typed only once instead of twice, moreover, the plugboard had 10 wires instead of 6. After the Enigma was updated, the Polish were no longer able to crack it.
Shortcomings and “Future” Improvement
It is obvious a clever method to reduce the possibilities of what a letter might be corresponding to. However after all reducing the possibilities, we still have to violently crack messages and so it no longer worked after the Germany updated Enigma. However, this method has inspired Alan Turing, who later developed the famous machine Bombe to crack Enigma.
Parts That Are Still Unclear
The enciphering process of the Enigma Machine and the deciphering of the Polish method is quite clear. What we still don’t quite understand is after Germany updated Enigma, how did Alan Turing use the deciphering method to crack Enigma as well as improved the complexity.
Key Contribution of the Polish Deciphering Method.
Basically, we conclude two big historical contributions of the Polish deciphering method. First, it once provided a way to crack the Enigma Machine before 1939. Second, it provided as a foundation to implement Turing’s deciphering machine, Bombe, which means it actually contributed a lot to the victory of the Allies in WWII.
Why We Choose This Topic
First, all three of us are interested in cryptography - enciphering and deciphering. After watching the film The Imitation Game, we got interested in the Enigma Machine. When we were looking up the Enigma Machine, we found that the Polish mathematician and cryptologist Marian Rejewski and the following Polish codebreakers made great contribution towards the cracking of Enigma. However, most people seem to only know Turing. Since the Polish provided the base for Turing to build Bombe, which finally cracked Enigma, we decide to introduce the Polish deciphering method.
Reference
“History - Enigma (Pictures, Video, Facts & News).” BBC, BBC, www.bbc.co.uk/history/topics/enigma.
Hern, Alex. “How Did the Enigma Machine Work?” The Guardian, Guardian News and Media, 14 Nov. 2014, www.theguardian.com/technology/2014/nov/14/how-did-enigma-machine-work-imitation-game.
Weiran Liu,”How did Turing decipher Enigma in Imitation Game?” Zhihu, 27 Feb. 2015, www.zhihu.com/question/28397034.
Numberphile. “158,962,555,217,826,360,000 (Enigma Machine) - Numberphile.” YouTube, YouTube, 10 Jan. 2013, www.youtube.com/watch?v=G2_Q9FoD-oQ.
Numberphile. “Flaw in the Enigma Code - Numberphile.” YouTube, YouTube, 14 Jan. 2013, www.youtube.com/watch?annotation_id=annotation_786414&feature=iv&src_vid=G2_Q9FoD-oQ&v=V4V2bpZlqx8.
Singh, Simon (26 January 2011). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Knopf Doubleday Publishing Group. ISBN 978-0-307-78784-2.
Team member contributions
Fanghui He:
How we encipher the message with Enigma;
Evaluation of Enigma’s ciphering ability;
Parts that are still unclear;
Key contributions of the Polish deciphering method.
Yining Hua:
Introduction and background of Enigma;
How to use Enigma;
The evaluation of the Polish deciphering method;
Shortcomings of the Polish deciphering method.
Qiaqia Ji:
How the Polish deciphering method works;
Evaluation of the Polish deciphering method;
Cultural significance of the topic;
German Update of the Enigma.